import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLinkList {
    class BinaryTreeNode{
        int val;
       BinaryTreeNode left;
       BinaryTreeNode right;
        public BinaryTreeNode(int val){
            this.val=val;
        }
    }
    private BinaryTreeNode root;//创建一个根节点
    public BinaryTreeNode createinary(){
        BinaryTreeNode node1=new BinaryTreeNode(1);
        BinaryTreeNode node2=new BinaryTreeNode(2);
        BinaryTreeNode node3=new BinaryTreeNode(3);
        BinaryTreeNode node4=new BinaryTreeNode(4);
        BinaryTreeNode node5=new BinaryTreeNode(5);
        BinaryTreeNode node6=new BinaryTreeNode(6);
        BinaryTreeNode node7=new BinaryTreeNode(7);
        BinaryTreeNode node8=new BinaryTreeNode(8);

        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        node5.right=node8;
        return node1;
        //二叉树要么是空树
        //非空：根节点、根节点的柞树、根节点的右树
        //空树其实是构建结束的条件
        //从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的
    }
    //NLR
    public void prevOrder(BinaryTreeNode root){
        if(root==null) return ;//这一步既是可以进行相关操作的判断，又是最后循环结束的条件。
        System.out.print(root.val);
        prevOrder(root.left);
        prevOrder(root.right);
    }
    public void inOrder(BinaryTreeNode root){
        if(root==null) return ;//这一步既是可以进行相关操作的判断，又是最后循环结束的条件。
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }
    public void postOrder(BinaryTreeNode root){
        if(root==null) return ;//这一步既是可以进行相关操作的判断，又是最后循环结束的条件。
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }
    //private int count=0;

    public int count=0;
    public void prevSize(BinaryTreeNode root){
       if(root==null) return ;
        count++;
        prevSize(root.left);
        prevSize(root.right);
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
    }
    public void inSize(BinaryTreeNode root){
        if(root==null) return ;
        inSize(root.left);
        count++;

        inSize(root.right);
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
    }
    public void postSize(BinaryTreeNode root){
        if(root==null) return ;
        postSize(root.left);
        postSize(root.right);
        count++;
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
    }
    //这里本质上还是借助子问题的思路
    //
    public int Size(BinaryTreeNode root){
        //使用：一个计数器
        if(root==null) return 0;
        int leftNodeSize =Size(root.left);
        //这里的两个可以更换位置，不影响，这里用的是子问题的思路
        //先怎样在怎样都无所五
        int rightNodeSize =Size(root.right);
        //不建议用三目表达式，会有重复的计算
        return 1+leftNodeSize+rightNodeSize;
    }
    public int getLeafNodeCount(BinaryTreeNode root){
        //这个是使用子问题思路，每个树都有自己的叶子个数，
        int leftTreeLeafNodeSize = 0;
        int rightTreeLeafNodeSize =0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        if(root.left==null&&root.right!=null){
            rightTreeLeafNodeSize =getLeafNodeCount(root.right);
        }
        if(root.left!=null&&root.right==null){
            leftTreeLeafNodeSize =getLeafNodeCount(root.left);
        }
        if(root.left!=null&&root.right!=null) {
            leftTreeLeafNodeSize = getLeafNodeCount(root.left);
            rightTreeLeafNodeSize = getLeafNodeCount(root.right);
        }
        return leftTreeLeafNodeSize+rightTreeLeafNodeSize;
    }
    //上面这个写法没有最开始判断null是不是空
    //所以后面多了两个if，并且还有
    public int getLeafSize(BinaryTreeNode root){
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        return getLeafSize(root.left)+getLeafSize(root.right);
    }
    public int LeafNodeCount=0;
    public void prevGetLeafNodeCount(BinaryTreeNode root) {
        if(root==null) return ;
        if(root.right==null&&root.left==null) {
            LeafNodeCount++;
        }
        prevGetLeafNodeCount(root.left);
        prevGetLeafNodeCount(root.right);
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
        return ;
    }
    public void inGetLeafNodeCount(BinaryTreeNode root) {
        if(root==null) return ;

        inGetLeafNodeCount(root.left);
        if(root.right==null&&root.left==null) {
            LeafNodeCount++;
        }
        inGetLeafNodeCount(root.right);
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
        return ;
    }
    public void postGetLeafNodeCount(BinaryTreeNode root) {
        if(root==null) return ;

        postGetLeafNodeCount(root.left);

        postGetLeafNodeCount(root.right);
        if(root.right==null&&root.left==null) {
            LeafNodeCount++;
        }
        //在这里的返回值起到的作用仅仅是结束这个函数的栈帧，我们不需要用访问到给我们一个具体的值
        //只要能访问，就++
        return ;
    }
    public int getKLevelNodeCount(BinaryTreeNode root,int key){
        //k层节点个数==左子树的k-1层节点个数+右子树的k-1层节点个数；
        if(root==null) return 0;
        if(key==1) return 1;
        int leftGetKLevelNodeCount= getKLevelNodeCount(root.left,key-1);
        int rightGetKLevelNodeCount= getKLevelNodeCount(root.right,key-1);
        return leftGetKLevelNodeCount+rightGetKLevelNodeCount;
    }
    public void levelOrder(BinaryTreeNode root,int key){
        if(root==null) return;
        Queue<Integer> queue=new LinkedList<>();
        //这个队列在每个栈帧里都会有

    }
    public void prevGetLevelNodeCount(BinaryTreeNode root,int key){
        //其实这个使用层序遍历更加的简单一些可能---按照完全二叉树的方式去保存，没有的地方记为空
    }
    public  int getHeight(BinaryTreeNode root) {
        //有一个巧妙的办法，用那个求k层节点的个数的办法，让k++
        //很抽象的方法
        for (int k = 1; k < Integer.MAX_VALUE; k++) {
            if (getKLevelNodeCount(root, k) == 0) {
                return k-1;
            }
        }
        return -1;
    }
    //用子问题的思路
    //二叉树的高度==左子树的高度和右子树高度的最大值+1；
    public int getHight2(BinaryTreeNode root){
        if(root==null) return 0;
        int left=getHight2(root.left);
        int right=getHight2(root.right);
        return left>right ? left+1:right+1;
    }
    public boolean find(BinaryTreeNode root,int key){
        if(root==null) return false;
        if(root.val==key) return true;
        boolean leftVal=find(root.left,key);
        if(leftVal==true){
            return true;
        }
        boolean rightVal=find(root.right,key);
        if(rightVal==true){
            return true;
        }
        return false;
    }
    //层序遍历：
    public void levelOrder(BinaryTreeNode root){
        //使用队列来辅助完成层序遍历
        //将第一层的放进去
        //先放左子树，然后放右子树
        //也可以用递归去实现
        if (root == null) {
            return ;
        }
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            BinaryTreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    public List<List<BinaryTreeNode>> levelOrder2(BinaryTreeNode root){
        //使用队列来辅助完成层序遍历
        //将第一层的放进去
        //先放左子树，然后放右子树
        //也可以用递归去实现
        List<List<BinaryTreeNode>> ret=new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //需要知道当前队列的大小
            //需要出四次，就相当于把这一层所有的节点都出队了。
            int  size=queue.size();
            List<BinaryTreeNode> tmp=new LinkedList<>();
            while(size!=0) {
                BinaryTreeNode cur = queue.poll();
                tmp.add(cur);
                size--;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(tmp);
        }

        return ret;
    }
    //判断一个二叉树是不是完全二叉树
    //保留null

}

class Solution {
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        //用子问题思路
//        //两个树相同==根节点相同+左子树相同+右子树相同
//
//        //这种情况:两个树都为空，那肯定就一样（或者两个左子树，两个右子树都为空，也代表左子树和右子树一样的
//        if(p==null&&q==null){
//            return true;
//        }
//        //这两种情况，已经结构不一样了，也不用去关心值一样不一样
//        if(p==null&&q!=null) return false;
//        if(q==null&&p!=null) return false;
//
//
//        boolean left=isSameTree(p.left,q.left);
//        boolean right=isSameTree(p.right,q.right);
//        //这种情况，两个都不为空，要是两个树的值/左子树的值/右子树的值一样，那么就可以判断结构一样了
//
////这一句才是真正的判断，其他的都是为了找到不符合的，然后他跳出
//        if(p.val==q.val&&left==true&&right==true){
//            return true;
//        }
//
//        return false;
//    }
//
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        //用子问题的方法
//        //判断一个树是不是另一棵树的子树
//        //判断一个树是不是另一个树的左子树/右子树
//        if(root==null&&subRoot==null) return true;
//        //这种情况应该不太可能，太离谱了
//        if(root==null&&subRoot!=null) return false;
//        if(root!=null&&subRoot==null) return true;
//        if(root.val==subRoot.val){
//            return isSameTree(root,subRoot);
//        }
//        if(root.left!=null){
//            return isSubtree(root.left,subRoot);
//        }else if(root.right!=null){
//            return isSubtree(root.right,subRoot);
//        }else{
//            return false;
//        }
//        return false;
//    }
}
